Pizza with 3n slices [House Robber II]¶
Time: O(N^2); Space: O(N); hard
There is a pizza with 3n slices of varying size, you and your friends will take slices of pizza as follows:
You will pick any pizza slice. Your friend Alice will pick next slice in anti clockwise direction of your pick. Your friend Bob will pick next slice in clockwise direction of your pick. Repeat until there are no more slices of pizzas. Sizes of Pizza slices is represented by circular array slices in clockwise direction.
Return the maximum possible sum of slice sizes which you can have.
Example 1:
Input: slices = [1,2,3,4,5,6]
Output: 10
Explanation:
Pick pizza slice of size 4, Alice and Bob will pick slices with size 3 and 5 respectively.
Then Pick slices with size 6,
Finally Alice and Bob will pick slice of size 2 and 1 respectively.
Total = 4 + 6.
Example 2:
Input: slices = [8,9,8,6,1,1]
Output: 16
Explanation:
Pick pizza slice of size 8 in each turn. If you pick slice with size 9 your partners will pick slices of size 8.
Example 3:
Input: slices = [4,1,2,5,8,3,1,9,7]
Output: 21
Example 4:
Input: slices = [3,1,2]
Output: 3
Constraints:
1 <= len(slices) <= 500
len(slices) % 3 == 0
1 <= slices[i] <= 1000
Hints:
By studying the pattern of the operations, we can find out that the problem is equivalent to: Given an integer array with size 3N, select N integers with maximum sum and any selected integers are not next to each other in the array.
The first one in the array is considered next to the last one in the array. Use Dynamic Programming to solve it.
1. Dynamic programming [O(N^2), O(N)]¶
[observation] 1. we can never take two adjacent slices 2. if we want some set of N / 3 non-adjacent slices, there is always a way to take
[proof] - for N = 3, it is obviously True. - for N’ = N + 3, - because it’s impossible to have only one unwanted slices between all wanted slices. if it’s true, there will be 3N’/2 unwanted slices rather than 2N’ unwanted ones, -><- - so we can always find a sequence of two unwanted slices with one wanted slice to take firstly, then we can find a way to take the remaining N ones by induction, QED better optimized space
[1]:
class Solution1(object):
"""
Time: O(N^2)
Space: O(N)
"""
def maxSizeSlices(self, slices):
"""
:type slices: List[int]
:rtype: int
"""
def maxSizeSlicesLinear(slices, start, end):
dp = [[0]*(len(slices)//3+1) for _ in range(2)]
for i in range(start, end):
for j in reversed(range(1, min(((i-start+1)-1)//2+1, len(slices)//3)+1)):
dp[i%2][j] = max(dp[(i-1)%2][j], dp[(i-2)%2][j-1] + slices[i])
return dp[(end-1)%2][len(slices)//3]
return max(maxSizeSlicesLinear(slices, 0, len(slices)-1),
maxSizeSlicesLinear(slices, 1, len(slices)))
[2]:
s = Solution1()
slices = [1,2,3,4,5,6]
assert s.maxSizeSlices(slices) == 10
slices = [8,9,8,6,1,1]
assert s.maxSizeSlices(slices) == 16
slices = [4,1,2,5,8,3,1,9,7]
assert s.maxSizeSlices(slices) == 21
slices = [3,1,2]
assert s.maxSizeSlices(slices) == 3
2. Dynamic programming¶
[3]:
class Solution2(object):
def maxSizeSlices(self, slices):
"""
:type slices: List[int]
:rtype: int
"""
def maxSizeSlicesLinear(slices, start, end):
dp = [[0]*(len(slices)//3+1) for _ in range(3)]
for i in range(start, end):
for j in range(1, min(((i-start+1)-1)//2+1, len(slices)//3)+1):
dp[i%3][j] = max(dp[(i-1)%3][j], dp[(i-2)%3][j-1] + slices[i])
return dp[(end-1)%3][len(slices)//3]
return max(maxSizeSlicesLinear(slices, 0, len(slices)-1),
maxSizeSlicesLinear(slices, 1, len(slices)))
[4]:
s = Solution2()
slices = [1,2,3,4,5,6]
assert s.maxSizeSlices(slices) == 10
slices = [8,9,8,6,1,1]
assert s.maxSizeSlices(slices) == 16
slices = [4,1,2,5,8,3,1,9,7]
assert s.maxSizeSlices(slices) == 21
slices = [3,1,2]
assert s.maxSizeSlices(slices) == 3